Link state (LS) routing protocols such as Open Shortest Path First (OSPF), Intermediate system to intermediate system (IS-IS), and Private Network-to-Network Interface (PNNI) (upon which Optical Signaling and Routing Protocol (OSRP) from Ciena Corporation is based) require an accurate view of the network topology (this includes knowledge regarding the presence of nodes and links, their network address, and their state (up/down) as well as the value of all link metrics (e.g., their cost)) in order to calculate optimal routes to a destination node. These LS routing protocols use topology-state update mechanisms to build a topology database at each node, typically conveying the topology status through flooding (flooding is defined as the broadcasting of control messages containing link/node status and reachablility information through every link on every node in the network).
OSPF uses link state advertisement (LSA), PNNI uses PNNI topology state elements (PTSE). Topology information in PNNI is distributed in PTSEs, which are encapsulated in PNNI topology state packets (PTSPs) and periodically flooded to other nodes in the domain through all available links. As with all LS protocols, both OSPF and PNNI use Hello messages to establish and maintain link adjacencies. Router/Switch nodes and links go up/down in the course of operation (due to fiber cuts, hardware/software failures, etc.); link state routing protocols employ a flooding mechanism to disseminate this “change of state” information throughout the autonomous system. Simply put, this means when a router gets a new LSA message, it sends that information out to all of its directly connected networks. Or, if one of the links on a router changes state or its cost, the router generates a new LSA, which is flooded/broadcast out to all of its ports. Unfortunately, congestion in LS protocols due to flooding of control messages (LSAs and PTSEs) has caused many problems in the past. It can arise for many different reasons and can result in widespread loss of topology database information and overload in flooding of topology database information. In some instances of network overload, failure and/or congestion, flooding mechanisms can overwhelm routing control processors and bring the network down. A number of data network outages have been reported by service providers where the recovery of the underlying LS protocols was inadequate.
Networks are being deployed in ever larger flat mesh networks with hundreds of nodes. For example, in the near future, it is anticipated that as many as 500-1000 nodes will be deployed as one autonomous system in an optical switching network. In such an environment, flooding as originally defined is clearly an impractical and unsustainable method. A node's control processor (even with multi-core processors) will become easily overwhelmed as failures occur and the time for the network to converge will take 100s of seconds, if not 1000s of seconds, which the customer will find unacceptable. Many flooding reduction methods have been proposed and implemented, but there are drawbacks to those techniques and so there is still room for improvement. An efficient protocol and topology is needed to make flooding efficient, thus enabling networks to scale to thousands of nodes. The problems associated with flooding are the single biggest reason inhibiting networks from scaling.
Standard bodies such as the Internet Engineering Task Force (IETF) and Asynchronous Transport Mode (ATM) Forum have recognized the problem with flooding and have standardized approaches to make it more efficient. The ATM Forum recommends the use of areas to divide a large network into smaller areas, which, in theory, confines the flooding to an area. The IETF also allows the use of areas and in addition, created the concept of the designated router. Two newer approaches have since been standardized that were originally intended for mobile ad hoc networks, but can be used anywhere flooding reduction is desired. One such approach OSPF-MDR (Mobile Ad Hoc Networks Designated Routers) generalizes the use of the designated router by allowing the selection a subset of nodes to functions as designated routers, with all such routers connected together in a connected dominating set. Routers use two-hop information to independently elect themselves as Mobile Ad Hoc Networks (MANET) designated routers, MANET Backup Designated Routers or MANET-Other routers.
Another approach employs the concept of multipoint relays (MPRs), called OSPF-MPR, where each node maintains a set of nodes called multipoint relays, which are a subset of one-hop neighbors whose connectivity covers the two-hop neighborhood. An MPR node is a node's one-hop neighbor which has been chosen to forward control packets. This approach also uses modified hello messages that convey two-hop neighborhood information to select the multipoint relays. The key problem with these approaches is that all nodes have to rerun these algorithms after they have received LSAs/TSEs, so the new backbone can take some time to be rebuilt. The use of “areas” have been found to increase and not reduce the amount of flooding, an informational RFC written by Mikkel Thorup documents some of the harmful effects of using OSPF areas, which include: peculiarities of area routing can result in “funny area routing”; areas are likely to increase information, especially if the number of border routers for a given area is bigger than the degree (number of incident links) for each internal router; simple link-failure can lead to an avalanche of distance changes flooding the network with the use of areas; and the use of “summarization” can lead to unintended infinite loops.
Approaches such as OSPF-MDR and OSPF-MPR require significant modifications to the OSPF standard where two new type-length-values (TLVs) are created: 1) A modified hello protocol that provides two-hop neighborhood information and 2) A new metric TLV. More importantly, all of these new messages have to get propagated throughout the network and get to every node where the algorithm has to be rerun and then the new flooding backbone is created. This is very inefficient; it can take hundreds of seconds in a large network where there are 100s of nodes. It would be much more desirable to have a mechanism that requires minimal changes to the existing standard. Secondly, it would be best if nodes close to the failure can dynamically repair the flooding backbone. The current methods require every node in the network to rerun the designated router selection algorithm with the slightest failure/change in the network topology. This results in the network taking a long time to converge, since all nodes have to first receive the update messages and then run the algorithm. It would be better if nodes closest to the fault only rerun the algorithm while all others are unaffected.